#include <iostream>

using namespace std;

void swap(int &a, int &b)
{
	int i = a;
	a = b;
	b = i;
}

//template<typename T, unsigned n>
//void Merge(T(*arr)[n], size_t left, size_t r, size_t right)
//{
//	if (left == right)
//		return;
//	// create new arrays
//	int lnum = r - left + 1, rnum = right - r;
//	T* pLarr = new int[lnum +1]();
//	T* pRarr = new int[rnum + 1]();
//	int i, j = 0;
//	for (i = 0; i < lnum; ++i)
//		pLarr[i] = (*arr)[left + i];
//	for (i = 0; i < rnum; ++i)
//		pRarr[i] = (*arr)[r + 1 + i];
//
//	i = j;
//	int k;
//	for (k = left; k <= right; ++k)
//	{
//		if (pLarr[i] > pRarr[j])
//		{
//			(*arr)[k] = pLarr[i];
//			++i;
//		}
//		else
//		{
//			(*arr)[k] = pRarr[j];
//			++j;
//		}
//	}
//
//	delete[] pLarr;
//	delete[] pRarr;
//}
template<typename T, unsigned n>
void Merge(T(*arr)[n], size_t left, size_t r, size_t right)
{
	if (left == right)
		return;
	// create new arrays

	int lnum = r - left + 1, rnum = right - r;
	T* pLarr = new int[lnum]();//这里并没有使用哨兵
	T* pRarr = new int[rnum]();
	int i, j = 0;
	for (i = 0; i < lnum; ++i)
		pLarr[i] = (*arr)[left + i];
	for (i = 0; i < rnum; ++i)
		pRarr[i] = (*arr)[r + 1 + i];

	i = j;
	int k;
	for (k = left; k < right; ++k)
	{
		if (pLarr[i] > pRarr[j])
		{
			(*arr)[k] = pLarr[i];
			++i;
		}
		else
		{
			(*arr)[k] = pRarr[j];
			++j;
		}
	}

	for (;
		i != lnum; ++i, ++k)
		(*arr)[k] = pLarr[i];

	for (;
		j != rnum; ++j, ++k)
		(*arr)[k] = pRarr[j];

	delete[] pLarr;
	delete[] pRarr;
}

template<typename T, unsigned n>
void MergeSort(T (*arr)[n], size_t left, size_t right)
{
	if (left >= right)
	{
		cout << (*arr)[right] << " ";
		return;
	}
	int r = (right + left) / 2;

	MergeSort(arr, left, r);
	MergeSort(arr, r+1, right);

	Merge(arr, left, r, right);
}

int main()
{
	int arr1[] = { 3, 2, 1, 5, 4 };
	MergeSort(&arr1, 0, 4);
	return 0;
}
